/*
 * 0196. Missing Number
 * 给出一个包含 0 .. N 中 N 个数的序列，找出0 .. N 中没有出现在序列中的那个数。
 * https://www.lintcode.com/problem/missing-number/description
 * 
 * 样例
 * N = 4 且序列为 [0, 1, 3] 时，缺失的数为2。
 * 
 * 挑战
 * 在数组上原地完成，使用O(1)的额外空间和O(N)的时间。
 * 
 * 2018.06.18 @jeyming
 */

package missing_number_0196;

import java.util.Arrays;

public class Missing_number_0196 {
    /**
     * @param nums: An array of integers
     * @return: An integer
     */
    public static int findMissing(int[] nums) {
        // write your code here
    	Arrays.sort(nums, 0, nums.length);
    	for(int i = 0; i <= (nums[nums.length - 1] + 1); ++i) {
    		if(i >= nums.length)
    			return i;
    		else if(i != nums[i])
    			return i;
    	}
    	return 0;
    }

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int nums[] = {0,1,3};
		System.out.println(findMissing(nums));

	}

}
